Correction du Sujet 04 - NSI 2025

Au départ, x = 10 et y = 10.
La boucle s'exécute 10 fois : à chaque tour, x diminue de 1 et y augmente de 1.
À la fin :

x = 0
y = 20

Un programme Python est un texte : il est composé de caractères, de retours à la ligne, d'espaces et de symboles.
On peut donc représenter ce texte par une chaîne de caractères Python, par exemple avec des triples guillemets.

Programme	Termine ?	Justification
programme3	Oui	x prend les valeurs 10, 8, 6, 4, 2, 0.
programme4	Non	x augmente de 2 à chaque tour et reste toujours strictement positif.
programme5	Oui	La condition x < 0 est fausse dès le départ car x = 10.
programme6	Non	x prend les valeurs 10, 6, 2, -2, -6, ... et n'atteint jamais 0.

La fonction exécute le programme donné en paramètre puis renvoie True si l'exécution se termine.
Elle ne répond pas au problème, car si le programme ne termine pas, alors exec(programme) ne termine pas non plus et la fonction ne renvoie jamais False.

L'algorithme de Boyer-Moore recherche un motif dans un texte en comparant les caractères du motif de droite à gauche.
Lorsqu'une différence est trouvée, il utilise cette information pour décaler le motif de plusieurs positions, au lieu de le décaler seulement d'une position. Cela évite de nombreuses comparaisons inutiles.

def arret_essai2(programme):
    return not recherche("while", programme)

On peut aussi écrire, si l'on n'utilise pas la fonction recherche :

def arret_essai2(programme):
    return "while" not in programme

Premier cas : la fonction peut renvoyer True alors que le programme ne s'arrête pas. Par exemple, un programme récursif infini ne contient pas forcément de boucle while :

def f():
    f()
f()

Second cas : la fonction peut renvoyer False alors que le programme s'arrête. Par exemple programme1 contient une boucle while, mais elle termine.

def terminaison_inverse(programme):
    if arret(programme):
        boucle_infinie()
    else:
        return None

Cette fonction termine quand le programme donné ne termine pas, et ne termine pas quand le programme donné termine.

On considère :

programme_paradoxal = "terminaison_inverse(programme_paradoxal)"

Supposons que exec(programme_paradoxal) termine. Alors arret(programme_paradoxal) vaut True, donc terminaison_inverse(programme_paradoxal) lance une boucle infinie. Contradiction.

Supposons maintenant que exec(programme_paradoxal) ne termine pas. Alors arret(programme_paradoxal) vaut False, donc terminaison_inverse(programme_paradoxal) termine. Contradiction.

Dans les deux cas, on obtient une contradiction.

La fonction arret supposée ne peut pas exister. Il est impossible d'écrire une fonction qui décide, pour tout programme Python, si ce programme termine ou non.

Cette impossibilité n'est pas due aux limites du langage Python. C'est un résultat théorique général : le problème de l'arrêt est indécidable pour tout langage de programmation suffisamment expressif.

La chaîne "SIX ANANAS" contient 10 caractères : S, I, X, une espace, A, N, A, N, A, S.
Chaque caractère est codé sur 1 octet, donc la taille est :

10 octets = 80 bits

Caractère	Code hexadécimal
S	53
I	49
X	58
espace	20
A	41
N	4E

Le codage de "SIX ANANAS" est donc :

53 49 58 20 41 4E 41 4E 41 53

Symbole	S	I	X	espace	A	N
Nombre d'occurrences	2	1	1	1	3	2

La somme des nombres d'occurrences correspond au nombre total de caractères du texte.
Ici :

2 + 1 + 1 + 1 + 3 + 2 = 10

def occurrence(texte):
    dico = {}
    for lettre in texte:
        if lettre in dico:
            dico[lettre] = dico[lettre] + 1
        else:
            dico[lettre] = 1
    return dico

Un arbre de Huffman possible est obtenu par les regroupements suivants :

I(1) + X(1) = 2
espace(1) + IX(2) = 3
S(2) + N(2) = 4
(espace-IX)(3) + A(3) = 6
(S-N)(4) + (espace-IX-A)(6) = 10

On obtient donc, par exemple, l'arbre suivant :

                 10
              /      \
             4        6
           /   \     / \
          S     N   3   A
                   / \
              espace  2
                     / \
                    I   X

Comme certains symboles ont le même nombre d'occurrences, plusieurs arbres de Huffman corrects sont possibles.

Le poids de la racine correspond au nombre total de caractères dans le texte.
Ici, le poids de la racine est donc 10.

Pour créer la table de codage, on utilise un parcours en profondeur de l'arbre, en ajoutant 0 quand on descend à gauche et 1 quand on descend à droite.

Avec l'arbre proposé à la question 6, on obtient :

Symbole	Code
S	00
N	01
espace	100
I	1010
X	1011
A	11

Le code de Huffman est de longueur variable car tous les symboles ne sont pas codés avec le même nombre de bits.
Par exemple, dans la table précédente, A est codé par 11, donc 2 bits, alors que I est codé par 1010, donc 4 bits.

On code caractère par caractère :

S  I     X     _    A  N  A  N  A  S
00 1010  1011  100  11 01 11 01 11 00

En concaténant tous les codes, on obtient :

0010101011100110111011100

Le texte compressé contient donc 25 bits avec cet arbre.

L'encombrement initial est de 80 bits et l'encombrement final est de 25 bits.
Le taux de compression vaut :

(80 - 25) / 80 = 55 / 80 = 0,6875

Le taux de compression est donc 68,75 %.
Ce résultat est bien dans l'ordre de grandeur indiqué dans le sujet : entre 20 % et 90 %.

SELECT id-kimono
FROM location
WHERE fin = '';

SELECT COUNT(id-kimono)
FROM kimono
WHERE taille-kimono = 130;

SELECT nom, prenom
FROM adherent
JOIN location
ON adherent.numero-licence = location.numero-licence
WHERE location.id-kimono = 42
AND location.fin = '';

UPDATE adherent
SET taille-adherent = taille-adherent + 10
WHERE taille-adherent < 160;

Il faut d'abord supprimer les locations faisant référence à ce kimono, puis supprimer le kimono lui-même.

DELETE FROM location
WHERE id-kimono = 25;

DELETE FROM kimono
WHERE id-kimono = 25;

Eddie Nirrer est né le 12/10/2021. Les cinq premières lettres du nom sont NIRRE.
Un numéro de licence possible est donc :

M12102021NIRRE01

Le premier caractère M indique un homme.
Les huit caractères suivants sont 23091974, donc la date de naissance est le 23/09/1974.
Les cinq caractères suivants sont MARTI. Un nom de famille possible est donc Martin.

'STEPHANIE'

tab_adherents[0]['numero-licence']

def nombre_adherents(table, annee):
    compteur = 0
    for adherent in table:
        if adherent['annee'] == annee:
            compteur = compteur + 1
    return compteur

def adherent_plus_age(table):
    annee_min = table[0]['annee']
    for adherent in table:
        if adherent['annee'] < annee_min:
            annee_min = adherent['annee']
    resultat = []
    for adherent in table:
        if adherent['annee'] == annee_min:
            resultat.append(adherent)
    return resultat

def verification_licence(adherent):
    numero = adherent['numero-licence']
    if len(numero) != 16:
        return False
    debut = adherent['sexe'] + adherent['jour'] + adherent['mois'] + adherent['annee'] + extraire(adherent['nom'].upper(), 0, 5)
    if extraire(numero, 0, 14) != debut:
        return False
    fin = extraire(numero, 14, 16)
    return '01' <= fin <= '99'